<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0//EN">
<HTML>
<HEAD>
<LINK REL=STYLESHEET TYPE="text/css" HREF="../stylesheet.css" TITLE="Style">
<META NAME="GENERATOR" CONTENT="Java2HTML Version 1.5">
<TITLE>jminusminus.NNaiveRegisterAllocator (Java2HTML)</TITLE>
</HEAD>
<BODY><TABLE id="Header" border="0" cellpadding="0" cellspacing="0" width="100%">
<tr>
<td colspan="2" width="33%">&nbsp;</td>
<td align="center" colspan="2" width="33%">
<font size="4">NNaiveRegisterAllocator.java</font>
</td>
<td align="right" colspan="2" width="33%">&nbsp;</td>
</tr>
</TABLE>
<pre ID="Classes">
<FONT ID="LN">1   </FONT><A NAME="1"></A><FONT ID="SingleLineComment">// Copyright 2013 Bill Campbell, Swami Iyer and Bahar Akbal-Delibas
<FONT ID="LN">2   </FONT><A NAME="2"></A></FONT>
<FONT ID="LN">3   </FONT><A NAME="3"></A><FONT ID="Package">package</FONT> jminusminus;
<FONT ID="LN">4   </FONT><A NAME="4"></A>
<FONT ID="LN">5   </FONT><A NAME="5"></A><FONT ID="Import">import</FONT> java.util.ArrayList;
<FONT ID="LN">6   </FONT><A NAME="6"></A><FONT ID="Import">import</FONT> java.util.LinkedList;
<FONT ID="LN">7   </FONT><A NAME="7"></A><FONT ID="Import">import</FONT> java.util.Queue;
<FONT ID="LN">8   </FONT><A NAME="8"></A><FONT ID="Import">import</FONT> <FONT ID="Static">static</FONT> jminusminus.NPhysicalRegister.*;
<FONT ID="LN">9   </FONT><A NAME="9"></A>
<FONT ID="LN">10  </FONT><A NAME="10"></A><FONT ID="FormalComment">/**
<FONT ID="LN">11  </FONT><A NAME="11"></A> * Implemets a naive register allocation method. Each interval is considered
<FONT ID="LN">12  </FONT><A NAME="12"></A> * live for the entire cfg. Intervals are assigned physical registers on a first
<FONT ID="LN">13  </FONT><A NAME="13"></A> * come basis. When we run out of registers, we reuse the ones already assigned
<FONT ID="LN">14  </FONT><A NAME="14"></A> * and spill.
<FONT ID="LN">15  </FONT><A NAME="15"></A> */</FONT>
<FONT ID="LN">16  </FONT><A NAME="16"></A>
<FONT ID="LN">17  </FONT><A NAME="17"></A><FONT ID="Public">public</FONT> <FONT ID="Class">class</FONT> NNaiveRegisterAllocator <FONT ID="Extends">extends</FONT> <A HREF="../jminusminus/NRegisterAllocator.java.html">NRegisterAllocator</A> {
<FONT ID="LN">18  </FONT><A NAME="18"></A>
<FONT ID="LN">19  </FONT><A NAME="19"></A>    <FONT ID="FormalComment">/**
<FONT ID="LN">20  </FONT><A NAME="20"></A>     * Construct a NNaiveRegisterAllocator.
<FONT ID="LN">21  </FONT><A NAME="21"></A>     * 
<FONT ID="LN">22  </FONT><A NAME="22"></A>     * @param cfg
<FONT ID="LN">23  </FONT><A NAME="23"></A>     *            an instance of a control flow graph.
<FONT ID="LN">24  </FONT><A NAME="24"></A>     */</FONT>
<FONT ID="LN">25  </FONT><A NAME="25"></A>
<FONT ID="LN">26  </FONT><A NAME="26"></A>    <FONT ID="Public">public</FONT> NNaiveRegisterAllocator(<A HREF="../jminusminus/NControlFlowGraph.java.html">NControlFlowGraph</A> cfg) {
<FONT ID="LN">27  </FONT><A NAME="27"></A>        <FONT ID="Super">super</FONT>(cfg);
<FONT ID="LN">28  </FONT><A NAME="28"></A>    }
<FONT ID="LN">29  </FONT><A NAME="29"></A>
<FONT ID="LN">30  </FONT><A NAME="30"></A>    <FONT ID="FormalComment">/**
<FONT ID="LN">31  </FONT><A NAME="31"></A>     * Build intervals with (naive) register allocation information in them.
<FONT ID="LN">32  </FONT><A NAME="32"></A>     */</FONT>
<FONT ID="LN">33  </FONT><A NAME="33"></A>
<FONT ID="LN">34  </FONT><A NAME="34"></A>    <FONT ID="Public">public</FONT> <FONT ID="Void">void</FONT> allocation() {
<FONT ID="LN">35  </FONT><A NAME="35"></A>        <FONT ID="SingleLineComment">// In this allocation scheme, each interval just has a single
<FONT ID="LN">36  </FONT><A NAME="36"></A></FONT>        <FONT ID="SingleLineComment">// range spanning the entire cfg.
<FONT ID="LN">37  </FONT><A NAME="37"></A></FONT>        <FONT ID="For">for</FONT> (<A HREF="../jminusminus/NInterval.java.html">NInterval</A> interval : cfg.intervals) {
<FONT ID="LN">38  </FONT><A NAME="38"></A>            NBasicBlock lastBlock = cfg.basicBlocks
<FONT ID="LN">39  </FONT><A NAME="39"></A>                    .get(cfg.basicBlocks.size() - <FONT ID="IntegerLiteral">1</FONT>);
<FONT ID="LN">40  </FONT><A NAME="40"></A>            <A HREF="../jminusminus/NLIRInstruction.java.html">NLIRInstruction</A> lastLir = lastBlock.lir
<FONT ID="LN">41  </FONT><A NAME="41"></A>                    .get(lastBlock.lir.size() - <FONT ID="IntegerLiteral">1</FONT>);
<FONT ID="LN">42  </FONT><A NAME="42"></A>            interval.ranges.add(<FONT ID="New">new</FONT> NRange(<FONT ID="IntegerLiteral">0</FONT>, lastLir.id));
<FONT ID="LN">43  </FONT><A NAME="43"></A>        }
<FONT ID="LN">44  </FONT><A NAME="44"></A>
<FONT ID="LN">45  </FONT><A NAME="45"></A>        <FONT ID="SingleLineComment">// Allocate any fixed registers (a0, ..., a3 and v0) that were
<FONT ID="LN">46  </FONT><A NAME="46"></A></FONT>        <FONT ID="SingleLineComment">// assigned during generation phase to the appropriate
<FONT ID="LN">47  </FONT><A NAME="47"></A></FONT>        <FONT ID="SingleLineComment">// interval.
<FONT ID="LN">48  </FONT><A NAME="48"></A></FONT>        <FONT ID="For">for</FONT> (<FONT ID="Int">int</FONT> i = <FONT ID="IntegerLiteral">0</FONT>; i &lt; <FONT ID="IntegerLiteral">32</FONT>; i++) {
<FONT ID="LN">49  </FONT><A NAME="49"></A>            <FONT ID="If">if</FONT> (cfg.registers.get(i) != <FONT ID="Null">null</FONT>) {
<FONT ID="LN">50  </FONT><A NAME="50"></A>                cfg.intervals.get(i).pRegister = (NPhysicalRegister) cfg.registers
<FONT ID="LN">51  </FONT><A NAME="51"></A>                        .get(i);
<FONT ID="LN">52  </FONT><A NAME="52"></A>            }
<FONT ID="LN">53  </FONT><A NAME="53"></A>        }
<FONT ID="LN">54  </FONT><A NAME="54"></A>
<FONT ID="LN">55  </FONT><A NAME="55"></A>        <FONT ID="SingleLineComment">// Assign stack offset (relative to fp) for formal parameters
<FONT ID="LN">56  </FONT><A NAME="56"></A></FONT>        <FONT ID="SingleLineComment">// fourth and above, and stack offset (relative to sp) for
<FONT ID="LN">57  </FONT><A NAME="57"></A></FONT>        <FONT ID="SingleLineComment">// arguments fourth or above.
<FONT ID="LN">58  </FONT><A NAME="58"></A></FONT>        <FONT ID="For">for</FONT> (NBasicBlock block : cfg.basicBlocks) {
<FONT ID="LN">59  </FONT><A NAME="59"></A>            <FONT ID="For">for</FONT> (<A HREF="../jminusminus/NLIRInstruction.java.html">NLIRInstruction</A> lir : block.lir) {
<FONT ID="LN">60  </FONT><A NAME="60"></A>                <FONT ID="If">if</FONT> (lir <FONT ID="InstanceOf">instanceof</FONT> NLIRLoadLocal) {
<FONT ID="LN">61  </FONT><A NAME="61"></A>                    NLIRLoadLocal loadLocal = (NLIRLoadLocal) lir;
<FONT ID="LN">62  </FONT><A NAME="62"></A>                    <FONT ID="If">if</FONT> (loadLocal.local &gt;= <FONT ID="IntegerLiteral">4</FONT>) {
<FONT ID="LN">63  </FONT><A NAME="63"></A>                        <A HREF="../jminusminus/NInterval.java.html">NInterval</A> interval = cfg.intervals
<FONT ID="LN">64  </FONT><A NAME="64"></A>                                .get(((NVirtualRegister) loadLocal.write)
<FONT ID="LN">65  </FONT><A NAME="65"></A>                                        .number());
<FONT ID="LN">66  </FONT><A NAME="66"></A>                        interval.spill = <FONT ID="True">true</FONT>;
<FONT ID="LN">67  </FONT><A NAME="67"></A>                        interval.offset = loadLocal.local - <FONT ID="IntegerLiteral">3</FONT>;
<FONT ID="LN">68  </FONT><A NAME="68"></A>                        interval.offsetFrom = OffsetFrom.FP;
<FONT ID="LN">69  </FONT><A NAME="69"></A>                    }
<FONT ID="LN">70  </FONT><A NAME="70"></A>                }
<FONT ID="LN">71  </FONT><A NAME="71"></A>            }
<FONT ID="LN">72  </FONT><A NAME="72"></A>        }
<FONT ID="LN">73  </FONT><A NAME="73"></A>
<FONT ID="LN">74  </FONT><A NAME="74"></A>        <FONT ID="SingleLineComment">// Allocate registers.
<FONT ID="LN">75  </FONT><A NAME="75"></A></FONT>        Queue&lt;<A HREF="../jminusminus/NInterval.java.html">NInterval</A>&gt; assigned = <FONT ID="New">new</FONT> LinkedList&lt;<A HREF="../jminusminus/NInterval.java.html">NInterval</A>&gt;();
<FONT ID="LN">76  </FONT><A NAME="76"></A>        <FONT ID="For">for</FONT> (<FONT ID="Int">int</FONT> i = <FONT ID="IntegerLiteral">32</FONT>, j = <FONT ID="IntegerLiteral">0</FONT>; i &lt; cfg.intervals.size(); i++) {
<FONT ID="LN">77  </FONT><A NAME="77"></A>            <A HREF="../jminusminus/NInterval.java.html">NInterval</A> interval = cfg.intervals.get(i);
<FONT ID="LN">78  </FONT><A NAME="78"></A>            <FONT ID="If">if</FONT> (interval.pRegister == <FONT ID="Null">null</FONT>) {
<FONT ID="LN">79  </FONT><A NAME="79"></A>                <FONT ID="If">if</FONT> (j &gt;= NPhysicalRegister.MAX_COUNT) {
<FONT ID="LN">80  </FONT><A NAME="80"></A>                    <FONT ID="SingleLineComment">// Pull out (from a queue) a register that's
<FONT ID="LN">81  </FONT><A NAME="81"></A></FONT>                    <FONT ID="SingleLineComment">// already assigned to another interval and
<FONT ID="LN">82  </FONT><A NAME="82"></A></FONT>                    <FONT ID="SingleLineComment">// re-assign it to this interval. But then
<FONT ID="LN">83  </FONT><A NAME="83"></A></FONT>                    <FONT ID="SingleLineComment">// we have a spill situation, so
<FONT ID="LN">84  </FONT><A NAME="84"></A></FONT>                    <FONT ID="SingleLineComment">// create an offset for the spill.
<FONT ID="LN">85  </FONT><A NAME="85"></A></FONT>                    <A HREF="../jminusminus/NInterval.java.html">NInterval</A> spilled = assigned.remove();
<FONT ID="LN">86  </FONT><A NAME="86"></A>                    spilled.spill = <FONT ID="True">true</FONT>;
<FONT ID="LN">87  </FONT><A NAME="87"></A>                    <FONT ID="If">if</FONT> (spilled.offset == -<FONT ID="IntegerLiteral">1</FONT>) {
<FONT ID="LN">88  </FONT><A NAME="88"></A>                        spilled.offset = cfg.offset++;
<FONT ID="LN">89  </FONT><A NAME="89"></A>                        spilled.offsetFrom = OffsetFrom.SP;
<FONT ID="LN">90  </FONT><A NAME="90"></A>                    }
<FONT ID="LN">91  </FONT><A NAME="91"></A>                    interval.pRegister = spilled.pRegister;
<FONT ID="LN">92  </FONT><A NAME="92"></A>                    interval.spill = <FONT ID="True">true</FONT>;
<FONT ID="LN">93  </FONT><A NAME="93"></A>                    <FONT ID="If">if</FONT> (interval.offset == -<FONT ID="IntegerLiteral">1</FONT>) {
<FONT ID="LN">94  </FONT><A NAME="94"></A>                        interval.offset = cfg.offset++;
<FONT ID="LN">95  </FONT><A NAME="95"></A>                        interval.offsetFrom = OffsetFrom.SP;
<FONT ID="LN">96  </FONT><A NAME="96"></A>                    }
<FONT ID="LN">97  </FONT><A NAME="97"></A>                } <FONT ID="Else">else</FONT> {
<FONT ID="LN">98  </FONT><A NAME="98"></A>                    <FONT ID="SingleLineComment">// Allocate free register to interval.
<FONT ID="LN">99  </FONT><A NAME="99"></A></FONT>                    NPhysicalRegister pRegister = NPhysicalRegister.regInfo[T0
<FONT ID="LN">100 </FONT><A NAME="100"></A>                            + j++];
<FONT ID="LN">101 </FONT><A NAME="101"></A>                    interval.pRegister = pRegister;
<FONT ID="LN">102 </FONT><A NAME="102"></A>                    cfg.pRegisters.add(pRegister);
<FONT ID="LN">103 </FONT><A NAME="103"></A>                }
<FONT ID="LN">104 </FONT><A NAME="104"></A>                assigned.add(interval);
<FONT ID="LN">105 </FONT><A NAME="105"></A>            }
<FONT ID="LN">106 </FONT><A NAME="106"></A>        }
<FONT ID="LN">107 </FONT><A NAME="107"></A>
<FONT ID="LN">108 </FONT><A NAME="108"></A>        <FONT ID="SingleLineComment">// Make sure that inputs of LIR instructions are not all
<FONT ID="LN">109 </FONT><A NAME="109"></A></FONT>        <FONT ID="SingleLineComment">// assigned the
<FONT ID="LN">110 </FONT><A NAME="110"></A></FONT>        <FONT ID="SingleLineComment">// same register. Also, Handle spills, i.e., generate loads
<FONT ID="LN">111 </FONT><A NAME="111"></A></FONT>        <FONT ID="SingleLineComment">// and
<FONT ID="LN">112 </FONT><A NAME="112"></A></FONT>        <FONT ID="SingleLineComment">// stores where needed.
<FONT ID="LN">113 </FONT><A NAME="113"></A></FONT>        <FONT ID="For">for</FONT> (<FONT ID="Int">int</FONT> i = <FONT ID="IntegerLiteral">1</FONT>; i &lt; cfg.basicBlocks.size(); i++) { <FONT ID="SingleLineComment">// We
<FONT ID="LN">114 </FONT><A NAME="114"></A></FONT>            <FONT ID="SingleLineComment">// ignore
<FONT ID="LN">115 </FONT><A NAME="115"></A></FONT>            <FONT ID="SingleLineComment">// block B0
<FONT ID="LN">116 </FONT><A NAME="116"></A></FONT>            NBasicBlock block = cfg.basicBlocks.get(i);
<FONT ID="LN">117 </FONT><A NAME="117"></A>            ArrayList&lt;<A HREF="../jminusminus/NLIRInstruction.java.html">NLIRInstruction</A>&gt; newLir = <FONT ID="New">new</FONT> ArrayList&lt;<A HREF="../jminusminus/NLIRInstruction.java.html">NLIRInstruction</A>&gt;();
<FONT ID="LN">118 </FONT><A NAME="118"></A>            <FONT ID="For">for</FONT> (<A HREF="../jminusminus/NLIRInstruction.java.html">NLIRInstruction</A> lir : block.lir) {
<FONT ID="LN">119 </FONT><A NAME="119"></A>                newLir.add(lir);
<FONT ID="LN">120 </FONT><A NAME="120"></A>            }
<FONT ID="LN">121 </FONT><A NAME="121"></A>            <FONT ID="For">for</FONT> (<A HREF="../jminusminus/NLIRInstruction.java.html">NLIRInstruction</A> lir : block.lir) {
<FONT ID="LN">122 </FONT><A NAME="122"></A>                <FONT ID="Int">int</FONT> id = lir.id;
<FONT ID="LN">123 </FONT><A NAME="123"></A>
<FONT ID="LN">124 </FONT><A NAME="124"></A>                <FONT ID="If">if</FONT> (lir.reads.size() == <FONT ID="IntegerLiteral">2</FONT>) {
<FONT ID="LN">125 </FONT><A NAME="125"></A>                    <A HREF="../jminusminus/NInterval.java.html">NInterval</A> input1 = cfg.intervals.get(
<FONT ID="LN">126 </FONT><A NAME="126"></A>                            lir.reads.get(<FONT ID="IntegerLiteral">0</FONT>).number()).childAt(id);
<FONT ID="LN">127 </FONT><A NAME="127"></A>                    <A HREF="../jminusminus/NInterval.java.html">NInterval</A> input2 = cfg.intervals.get(
<FONT ID="LN">128 </FONT><A NAME="128"></A>                            lir.reads.get(<FONT ID="IntegerLiteral">1</FONT>).number()).childAt(id);
<FONT ID="LN">129 </FONT><A NAME="129"></A>                    <FONT ID="If">if</FONT> (input1.pRegister == input2.pRegister) {
<FONT ID="LN">130 </FONT><A NAME="130"></A>                        input2.pRegister = NPhysicalRegister.regInfo[T0
<FONT ID="LN">131 </FONT><A NAME="131"></A>                                + (input2.pRegister.number() + <FONT ID="IntegerLiteral">1</FONT>)
<FONT ID="LN">132 </FONT><A NAME="132"></A>                                % NPhysicalRegister.MAX_COUNT];
<FONT ID="LN">133 </FONT><A NAME="133"></A>                    }
<FONT ID="LN">134 </FONT><A NAME="134"></A>                }
<FONT ID="LN">135 </FONT><A NAME="135"></A>
<FONT ID="LN">136 </FONT><A NAME="136"></A>                <FONT ID="SingleLineComment">// Loads.
<FONT ID="LN">137 </FONT><A NAME="137"></A></FONT>                <FONT ID="For">for</FONT> (<FONT ID="Int">int</FONT> j = <FONT ID="IntegerLiteral">0</FONT>; j &lt; lir.reads.size(); j++) {
<FONT ID="LN">138 </FONT><A NAME="138"></A>                    <A HREF="../jminusminus/NInterval.java.html">NInterval</A> input = cfg.intervals.get(
<FONT ID="LN">139 </FONT><A NAME="139"></A>                            lir.reads.get(j).number()).childAt(id);
<FONT ID="LN">140 </FONT><A NAME="140"></A>                    <FONT ID="If">if</FONT> (input.spill) {
<FONT ID="LN">141 </FONT><A NAME="141"></A>                        NLIRLoad load = <FONT ID="New">new</FONT> NLIRLoad(block, id
<FONT ID="LN">142 </FONT><A NAME="142"></A>                                - lir.reads.size() + j, input.offset,
<FONT ID="LN">143 </FONT><A NAME="143"></A>                                input.offsetFrom, input.pRegister);
<FONT ID="LN">144 </FONT><A NAME="144"></A>                        newLir.add(newLir.indexOf(lir), load);
<FONT ID="LN">145 </FONT><A NAME="145"></A>                    }
<FONT ID="LN">146 </FONT><A NAME="146"></A>                }
<FONT ID="LN">147 </FONT><A NAME="147"></A>
<FONT ID="LN">148 </FONT><A NAME="148"></A>                <FONT ID="SingleLineComment">// Stores.
<FONT ID="LN">149 </FONT><A NAME="149"></A></FONT>                <FONT ID="If">if</FONT> (lir.write != <FONT ID="Null">null</FONT>) {
<FONT ID="LN">150 </FONT><A NAME="150"></A>                    <A HREF="../jminusminus/NInterval.java.html">NInterval</A> output = cfg.intervals.get(lir.write.number());
<FONT ID="LN">151 </FONT><A NAME="151"></A>                    <FONT ID="If">if</FONT> (output.spill) {
<FONT ID="LN">152 </FONT><A NAME="152"></A>                        NLIRStore store = <FONT ID="New">new</FONT> NLIRStore(block, id + <FONT ID="IntegerLiteral">1</FONT>,
<FONT ID="LN">153 </FONT><A NAME="153"></A>                                output.offset, output.offsetFrom, lir.write);
<FONT ID="LN">154 </FONT><A NAME="154"></A>                        newLir.add(newLir.indexOf(lir) + <FONT ID="IntegerLiteral">1</FONT>, store);
<FONT ID="LN">155 </FONT><A NAME="155"></A>                    }
<FONT ID="LN">156 </FONT><A NAME="156"></A>                }
<FONT ID="LN">157 </FONT><A NAME="157"></A>            }
<FONT ID="LN">158 </FONT><A NAME="158"></A>            block.lir = newLir;
<FONT ID="LN">159 </FONT><A NAME="159"></A>        }
<FONT ID="LN">160 </FONT><A NAME="160"></A>    }
<FONT ID="LN">161 </FONT><A NAME="161"></A>
<FONT ID="LN">162 </FONT><A NAME="162"></A>}</pre>
</BODY>
</HTML>